package com.liufei1988.sort;

/**
 * 插入排序：插入排序的思想是取未排序的区间中的元素，在已排序区间中找到合适的位置将其插入，并保证排序区间数据一致有序
 */
public class InsertSort {

    public static void testInsertSort(int[] a,int n){
        if (n<=1) return;
        for (int i=0;i<n;i++){
            int value=a[i];
            int j=i-1;
            for (;j>=0;--j){
                if (a[j]>value){
                    a[j+1]=a[j];//数据移动
                }else {
                    break;
                }
            }
            a[j+1]=value;
            for (int ss:a){
                System.out.print(ss+" ");
            }
            System.out.println();
        }

    }

    // 插入排序，a表示数组，n表示数组大小
    public void insertionSort(int[] a, int n) {
        if (n <= 1) return;

        for (int i = 1; i < n; ++i) {
            int value = a[i];
            int j = i - 1;
            // 查找插入的位置
            for (; j >= 0; --j) {
                if (a[j] > value) {
                    a[j+1] = a[j];  // 数据移动
                } else {
                    break;
                }
            }
            a[j+1] = value; // 插入数据
        }
    }
    public static void main(String[] args) {
        int[] a={10,9,11,7,31,0,5};
        testInsertSort(a,a.length);
    }
}
